/*
 * This file is part of aion-engine <aion-engine.com>
 *
 * aion-engine is private software: you can redistribute it and or modify
 * it under the terms of the GNU Lesser Public License as published by
 * the Private Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * aion-engine is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser Public License for more details.
 *
 * You should have received a copy of the GNU Lesser Public License
 * along with aion-engine.  If not, see <http://www.gnu.org/licenses/>.
 */
package com.aionengine.gameserver.utils.collections;

import javax.annotation.concurrent.ThreadSafe;
import java.util.AbstractQueue;
import java.util.Iterator;
import java.util.Queue;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

/**
 * Optimistic approach to lock-free FIFO queue;
 * E. Ladan-Mozes and N. Shavit algorithm, less CAS failures when enqueueing,
 * if compared with Michael and Scott Nonblocking Queue, in ConcurrentLinkedQueue
 */
@ThreadSafe
public class OptimisticLinkedQueue<E> extends AbstractQueue<E> implements Queue<E>, java.io.Serializable {

    private static final long serialVersionUID = -3445502502831420722L;

    private static class Node<E> {

        private volatile E item;
        private volatile Node<E> next;
        private volatile Node<E> prev;

        @SuppressWarnings("unused")
        Node(E x) {
            item = x;
            next = null;
            prev = null;
        }

        Node(E x, Node<E> n) {
            item = x;
            next = n;
            prev = null;
        }

        E getItem() {
            return item;
        }

        @SuppressWarnings("unused")
        void setItem(E val) {
            this.item = val;
        }

        Node<E> getNext() {
            return next;
        }

        void setNext(Node<E> val) {
            next = val;
        }

        Node<E> getPrev() {
            return prev;
        }

        void setPrev(Node<E> val) {
            prev = val;
        }
    }

    @SuppressWarnings("rawtypes")
    private static final AtomicReferenceFieldUpdater<OptimisticLinkedQueue, Node> tailUpdater = AtomicReferenceFieldUpdater
            .newUpdater(OptimisticLinkedQueue.class, Node.class, "tail");
    @SuppressWarnings("rawtypes")
    private static final AtomicReferenceFieldUpdater<OptimisticLinkedQueue, Node> headUpdater = AtomicReferenceFieldUpdater
            .newUpdater(OptimisticLinkedQueue.class, Node.class, "head");

    private boolean casTail(Node<E> cmp, Node<E> val) {
        return tailUpdater.compareAndSet(this, cmp, val);
    }

    private boolean casHead(Node<E> cmp, Node<E> val) {
        return headUpdater.compareAndSet(this, cmp, val);
    }

    /**
     * Pointer to the head node, initialized to a dummy node. The first actual node is at head.getPrev().
     */
    private transient volatile Node<E> head = new Node<E>(null, null);
    /**
     * Pointer to last node on list
     */
    private transient volatile Node<E> tail = head;

    /**
     * Creates a <tt>OptimisticLinkedQueue</tt> that is initially empty.
     */
    public OptimisticLinkedQueue() {
    }

    AtomicInteger count = new AtomicInteger();

    /**
     * Enqueues the specified element at the tail of this queue.
     */
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        Node<E> n = new Node<E>(e, null);
        for (; ; ) {
            Node<E> t = tail;
            n.setNext(t);
            count.incrementAndGet();
            if (casTail(t, n)) {
                t.setPrev(n);
                return true;
            }
        }
    }

    /**
     * Dequeues an element from the queue. After a successful casHead, the prev and next pointers of the dequeued node are
     * set to null to allow garbage collection.
     */
    public E poll() {
        for (; ; ) {
            Node<E> h = head;
            Node<E> t = tail;
            Node<E> first = h.getPrev();
            if (h == head) {
                if (h != t) {
                    if (first == null) {
                        fixList(t, h);
                        continue;
                    }
                    E item = first.getItem();
                    if (casHead(h, first)) {
                        h.setNext(null);
                        h.setPrev(null);
                        count.decrementAndGet();
                        return item;
                    }
                } else
                    return null;
            }
        }
    }

    /**
     * Fixing the backwards pointers when needed
     */
    private void fixList(Node<E> t, Node<E> h) {
        Node<E> curNodeNext;
        Node<E> curNode = t;
        while (h == this.head && curNode != h) {
            curNodeNext = curNode.getNext();
            curNodeNext.setPrev(curNode);
            curNode = curNode.getNext();
        }
    }

    public void clear() {
        while (poll() != null) ;
    }

    public int leaveTail() {
        E elem = null;
        E elem1 = null;
        int removed = 0;
        while ((elem = poll()) != null) {
            elem1 = elem;
            removed++;
        }
        if (elem1 != null) {
            removed--;
            offer(elem1);
        }
        return removed;
    }

    @Override
    public E peek() {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<E> iterator() {
        throw new UnsupportedOperationException();
    }

    @Override
    public int size() {
        return count.get();
    }
}
